/**
 * 1646. 获取生成数组中的最大值
 */
public class GetMaximumGenerated {
    public int getMaximumGenerated(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        int max = 1;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 1; i < (n % 2 == 0 ? n / 2 : n / 2 + 1); i++) {
            int a = dp[2 * i] = dp[i];
            int b = dp[2 * i + 1] = dp[i] + dp[i + 1];
            max = Math.max(max, Math.max(a, b));
        }
        return max;
    }
}
